Multiplicative Order
   HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, given a positive integer ''n'' and an
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
''a''
coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
to ''n'', the multiplicative order of ''a'' modulo ''n'' is the smallest positive integer ''k'' such that a^k\ \equiv\ 1 \pmod n. In other words, the multiplicative order of ''a'' modulo ''n'' is the order of ''a'' in the
multiplicative group In mathematics and group theory, the term multiplicative group refers to one of the following concepts: *the group under multiplication of the invertible elements of a field, ring, or other structure for which one of its operations is referre ...
of the units in the ring of the integers
modulo In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation. Given two positive numbers and , mo ...
''n''. The order of ''a'' modulo ''n'' is sometimes written as \operatorname_n(a).


Example

The powers of 4 modulo 7 are as follows: : \begin 4^0 &= 1 &=0 \times 7 + 1 &\equiv 1\pmod7 \\ 4^1 &= 4 &=0 \times 7 + 4 &\equiv 4\pmod7 \\ 4^2 &= 16 &=2 \times 7 + 2 &\equiv 2\pmod7 \\ 4^3 &= 64 &=9 \times 7 + 1 &\equiv 1\pmod7 \\ 4^4 &= 256 &=36 \times 7 + 4 &\equiv 4\pmod7 \\ 4^5 &= 1024 &=146 \times 7 + 2 &\equiv 2\pmod7 \\ \vdots\end The smallest positive integer ''k'' such that 4''k'' ≡ 1 (mod 7) is 3, so the order of 4 (mod 7) is 3.


Properties

Even without knowledge that we are working in the multiplicative group of integers modulo n, we can show that ''a'' actually has an order by noting that the powers of ''a'' can only take a finite number of different values modulo ''n'', so according to the pigeonhole principle there must be two powers, say ''s'' and ''t'' and without loss of generality ''s'' > ''t'', such that ''a''''s'' ≡ ''a''''t'' (mod ''n''). Since ''a'' and ''n'' are
coprime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...
, ''a'' has an inverse element ''a''−1 and we can multiply both sides of the congruence with ''a''−''t'', yielding ''a''''s''−''t'' ≡ 1 (mod ''n''). The concept of multiplicative order is a special case of the order of group elements. The multiplicative order of a number ''a'' modulo ''n'' is the order of ''a'' in the
multiplicative group In mathematics and group theory, the term multiplicative group refers to one of the following concepts: *the group under multiplication of the invertible elements of a field, ring, or other structure for which one of its operations is referre ...
whose elements are the residues modulo ''n'' of the numbers coprime to ''n'', and whose group operation is multiplication modulo ''n''. This is the
group of units In algebra, a unit or invertible element of a ring is an invertible element for the multiplication of the ring. That is, an element of a ring is a unit if there exists in such that vu = uv = 1, where is the multiplicative identity; the ele ...
of the ring Z''n''; it has ''φ''(''n'') elements, φ being
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
, and is denoted as ''U''(''n'') or ''U''(Z''n''). As a consequence of Lagrange's theorem, the order of ''a'' (mod ''n'') always divides ''φ''(''n''). If the order of ''a'' is actually equal to ''φ''(''n''), and therefore as large as possible, then ''a'' is called a primitive root modulo ''n''. This means that the group ''U''(''n'') is cyclic and the residue class of ''a'' generates it. The order of ''a'' (mod ''n'') also divides λ(''n''), a value of the Carmichael function, which is an even stronger statement than the divisibility of ''φ''(''n'').


Programming languages

* Maxima CAS: zn_order (a, n) * Wolfram Language: MultiplicativeOrder , n* Rosetta Code - examples of multiplicative order in various languagesrosettacode.org - examples of multiplicative order in various languages
/ref>


See also

* Discrete logarithm *
Modular arithmetic In mathematics, modular arithmetic is a system of arithmetic operations for integers, other than the usual ones from elementary arithmetic, where numbers "wrap around" when reaching a certain value, called the modulus. The modern approach to mo ...


References

*


External links

* {{DEFAULTSORT:Multiplicative Order Modular arithmetic